import java.util.ArrayList;
import java.util.List;

/**
 * @author LKQ
 * @date 2022/1/21 11:51
 * @description 回溯
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        solution2.readBinaryWatch(9);
    }

    public static List<String> result ;
    public List<String> readBinaryWatch(int turnOn) {
        result = new ArrayList<>();
        if(turnOn < 0 ) {
            return result;
        }
        //LED灯，前四个为小时，后六个为分钟
        int[] nums = new int[]{8,4,2,1,32,16,8,4,2,1};
        backTrack(turnOn, nums,0,0,0);
        return result;
    }
    public void backTrack(int turnOn,int[] nums,int start,int hour,int minute){
        if(turnOn == 0) {
            //判断时间是否正确
            if(hour> 11||minute>59) {
                return;
            }
            StringBuilder tmp=new StringBuilder();
            //小时
            tmp.append(hour + ":" + (minute < 10 ? "0" : "") + minute);
            result.add(new String(tmp));
            return;
        }
        for(int i=start;i<nums.length;i++){
            /*回溯做选择*/
            //判断是小时还是分钟
            if ( i < 4){
                hour+=nums[i];
            } else {
                minute+=nums[i];
            }
            //递归
            backTrack(turnOn - 1,nums,i+1, hour, minute);
            /*回溯取消选择*/
            if( i < 4) {
                hour-=nums[i];
            } else {
                minute-=nums[i];
            }
        }
    }
}
